This invention relates to the field of operating systems for digital computers, particularly digital computers wherein multiple tasks are scheduled for execution by one or more processors.
It is common in digital computers to have more than one task in a state ready for execution at the same time. In mainframe computers and minicomputers, these tasks can consist of batch processing jobs, users on a timesharing system, and system tasks used for sending output to printers. Multitasking is now present in microcomputer and even hand-held computer based systems &lt;&lt;coverage&gt;&gt;. While the user of a microcomputer or hand-held computer system may only be aware of the primary task being directed by their actions, other tasks may be handling functions such as electronic mail, calendar services, handwriting recognition, and the like.
In multitasking environments, when there is more than one task that is ready for execution, the operating system must schedule the order in which tasks will be executed by one or more processors.
A known scheduling method associates priorities with each task; at each scheduling interval, the task with the highest priority is selected for execution. A problem with this priority based scheduling is that lower priority tasks will not execute as long as a higher priority task is available for execution; this problem is known as lockout. While there are modifications to priority scheduling (such as preemptive scheduling, and applying small increments in priority for a short period of time based on events, both explained below) these methods do not solve the lockout problem, and add to the complexity of the scheduling process.